In recent years, storage devices using nonvolatile memories such as flash memories receive much attention as memory devices of portable apparatus handling music or video image data.
On the structure of the flash memory, explanation is given by taking the case of a 512M bits NAND type flash memory as an example.
FIG. 2 is a structural example of physical block of a 512M bits flash memory. One flash memory consists of 4096 blocks. This block forms a basic unit of erasing. One block is further divided into 32 pages. One page forms a basic unit of readout and writing. Capacity of one page is 528 bytes, among which 512 bytes are for a data area and remaining 16 bytes are for a redundant area. The data area is an area to be used by the user, the redundant area is an area to be used by the system control part of a nonvolatile flash memory storage device.
Each data of a flash memory of an embodiment is 1 at an erased state (where it is erased and is not recorded). Therefore, to write 1 in a flash memory may be replaced by writing nothing.
FIG. 3 is an example of a structural drawing of a physical block of a prior art flash memory. FIG. 3 represents main data written in a redundant area of one physical block. In a redundant area of an initial page, three, which are a writing done flag 101, a logical address 102 and a flag 1103 that is an block data invalidation flag, are placed. On these individual data, explanation is given later.
FIG. 4 is a drawing showing a relationship between the logical address and the physical address. In a nonvolatile memory storage device using flash memories, a logical address specified from outside and a physical address placed in a flash memory are not same in general. This is because such inconvenience happens as that, if making those addresses same, addresses of blocks at which malfunction occurs in the flash memory cannot be used, applications are made to bear load or, the block corresponding to that address easily exceeds a guaranteed number of rewriting times in a short time period, resulting in a short life time in such a system in which writing occurs frequently in a particular address.
Therefore, as is shown in FIG. 3, the physical block memorizes which logical address this physical block is assigned within the redundant area. In general the system control part of the nonvolatile memory storage device reads out the logical address information written in the redundant areas of all the flash memories at the starting time of power source and then generates a logical-physical address conversion table for converting logical addresses and physical addresses on a RAM as shown in FIG. 5. The system control part identifies a physical address with respect to a logical address specified from outside using the logical-physical address conversion table at the time of command process, and then makes access to the physical address.
Using FIG. 6 to FIG. 8, explanation will be given on a prior art general writing process. FIG. 6 is a one-block writing process schematic flowchart. FIG. 7 is a detailed flowchart of a new data writing process part in a step 603 of FIG. 6. FIG. 8 is a detailed flowchart of a redundant area data generating process part in a step 706 of FIG. 7.
In FIG. 6, at a step 601 erased blocks are searched from the entry table. The entry table is a lookup table of blocks which are already erased and not yet written. The entry table is a table generated on a RAM by reading out the writing done flags in the redundant areas of all of the flash memories at the starting time of the power-source, similar to the above-mentioned logical-physical address conversion table. Updating the entry table at a step 602, thereby erased blocks are acquired. Data are written in the acquired block at a step 603 (details are shown in FIGS. 7 and 8). At a step 604 it is judged from the logical-physical address conversion table whether there is an old block or not. In case where there is an old block, process proceeds to a step 605. At the step 605, 0 (invalid) is overwritten on the flag 1 located in the redundant area of the top page of the old block, thus invalidating the old block. In case where there is not an old block, process proceeds to a step 606 skipping the step 605. At the step 606, the physical address of the old block of the logical-physical address conversion table is rewritten to the physical address of the new block, and this flowchart is terminated.
Now, there are two methods in the erasing process of the old data; a method in which data are erased physically and a method in which an apparent erasing is done by marking the flag representing that data are invalid and then physical erasing is done at a different timing. The latter is employed generally and the flowchart of FIG. 6 has also been explained in this method. This is because the overwriting of flags is faster than the physical erasing in the flash memory. And it is because the writing speed can be made faster as the whole by an amount of time during which writing and erasing are simultaneously done by erasing invalid-marked blocks physically simultaneously while writing is done in other flash memory chip in a nonvolatile memory device comprised of a plural number of flash memory chips.
In FIG. 7, at a step 701 a page counter provided in the RAM is set the initial value (1). At a step 702, it is judged whether it is the page in which the data given from the host is to be written or not. If it is the page in which the data given from the host is to be written, process proceeds to a step 703 and data are inputted by an amount of one page from the host. If it is not the page in which the data given from the host is to be written, process proceeds to a step 704 and data are read out by an amount of one page from the old block. At a step 705 data are set in the data area, and at a step 706 data are set in the redundant area (details are shown in FIG. 8). At a step 707, one page is written. At a step 708, 1 is added to the page counter. At a step 709, it is judged whether the page counter is equal to or more than 33 or not. Process from step 702 to step 709 is repeated during a time period that the page counter is less than 33. When the page counter becomes 33, this flowchart is terminated.
The above-mentioned process from the step 702 to the step 704 in FIG. 7 is a process necessary because a unit of writing is a page while a unit of erasing is a block, and it is called as a wrap up process. Namely, since previous data should be retained as they were in the pages except the writing page when writing data are given in a page unit from outside, the data from an old block which are to be changed are read out, these data are combined, and writing of an amount of one block is done. Depending on whether it is a starting page or a terminating page of writing, there are a first-half wrap up process and a second-half wrap up process.
In FIG. 8, at a step 801, whether it is the top page or not is judged. In the case of the top page, process proceeds to a step 802 and the writing done flag 101 is set 0 (Writing was done.). At a step 803, a logical address assigned from the host is set in the logical address 102. At a step 804, the flag 1103 is set 1 (not invalid), and then this flowchart is terminated. At the step 801, in the case where it is not the top page, this flowchart is terminated.
In such a system, in a case where a forced interruption is caused by shutdown of a power supply for the memory device, a reset command to the memory device or the like during overwriting of the blocks, it results in two physical addresses existing for one identical logical address. This phenomenon takes place in such a case where the interruption takes place during writing of new block data (step 603), or after the new block data writing process (step 603) has been completed and before the old block data (step 604) ought to have been invalidated in the above-mentioned process.
Let us consider a method of registering the physical address of either block in the logical-physical address conversion table and leaving the other block in which block data and a logical address are written as they are in the process of generating an initial logical-physical address conversion table after this phenomenon took place. In this case, when the power supply is turned on again after erasing the block that was registered in the above-mentioned state, the physical address of the other block (block left as it is), which ought to have been erased, is registered for the logical address in a logical-physical address conversion table which is newly generated in a RAM. As a result, such a phenomenon that the address which ought to have been erased is not actually erased happens.
And in the case where the interruption takes place under the state in which the same logical address is written in a block in which old block data are written and in a block in which new block data are written, and then the power supply is turned on again, there is a possibility that the physical address of the block in which old block data are written is registered in the logical-physical address conversion table. In this case, new block data result in being lost. A phenomenon crucial to the system takes place after all.
Therefore conventionally, a process of invalidating one block and dissolving duplication has been conducted in the case where duplication of physical addresses for the same logical address is found at the time of generating a logical-physical conversion table at the beginning. As for the selecting method of these two blocks, such a method has been employed wherein two block data were both read out and block without error was selected by confirming the error correction code provided on each page, or a block in which data ware written up to the last page was selected.
However, necessity of executing a generation process of the logical-physical address conversion table at high speed is emerging in connection with the increase of the capacity of flash memories and nonvolatile memory storage devices, and the above-mentioned duplication resolving process is now becoming an large obstacle against realizing the high-speed process. Although it is commonly employed to generate a logical-physical address conversion table by hardware, a method, in which process of the address duplication information are taken over by the software, largely lowers the speed of generating the logical-physical address conversion table. Even if all the processes are done by hardware, if a conventional complicated decision process is employed, area size occupied by the hardware increases, eventually introducing a cost increase. Furthermore, even in such a state in which duplicated blocks are both written correctly up to the last page physically, there is a case where a correct block should be selected depending on the contents of the data area. For example, it is a case where process of invalidating the old data only after confirming that they are correct by confirming the error correction codes included in those data or by judging whether those data values are abnormal values or not in an overwriting process and after new data are written is necessary for data. In such a case, the problem cannot be solved by such a method as simply selecting the data having a later writing time. For example, although there is necessity of executing processes of scanning up to the data area depending upon individual situation of data, then determining and selecting a correct block, it is difficult to realize all of these processes by hardware.
The present invention has been done in consideration of such problems. It purports to offer a memory device wherein the logical-physical address conversion table can be generated at high speed along with ensuring the reliability with addition of a simple configuration.